package com.leetcode.partition2;

import com.leetcode.common.TreeNode;

import java.util.LinkedList;

/**
 * @author `RKC`
 * @date 2021/8/17 9:01
 */
public class LC101对称二叉树 {

    public static boolean isSymmetric(TreeNode root) {
        return recursion(root.left, root.right);
    }

    private static boolean iteration(TreeNode root) {
        if (root == null) return true;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root.left);
        queue.add(root.right);
        while (!queue.isEmpty()) {
            //取出一对节点比较，并再之后进行对称添加，保持这个原理，数据结构使用栈也可以实现
            TreeNode leftNode = queue.pollFirst();
            TreeNode rightNode = queue.pollFirst();
            if (leftNode == null && rightNode == null) continue;
            if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
                return false;
            }
            //镜像地添加结点到队列
            queue.add(leftNode.left);
            queue.add(rightNode.right);
            queue.add(leftNode.right);
            queue.add(rightNode.left);
        }
        return true;
    }

    private static boolean recursion(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 != null) return false;
        else if (root1 != null && root2 == null) return false;
        else if (root1 == null) return true;
        else if (root1.val != root2.val) return false;
        return recursion(root1.left, root2.right) && recursion(root1.right, root2.left);
    }
}
